Ông sinh ngày 7 tháng 3 năm 1957, tại Bà Chiểu, Sài Gòn. Ông là con thứ tư của ông Mai Văn Phú, một công nhân Sở Trường Tiền Gia Định, người Nam Định. Thân phụ ông cũng là một người mê cờ, nên ông cũng được kế thừa các kỹ thuật cờ và cũng sớm bộc lộ năng khiếu từ lúc 12, 13 tuổi.

Năm 1976, ông gia nhập Lực lượng Thanh niên Xung phong Thành phố Hồ Chí Minh. Tuy nhiên, 3 năm sau, ông bị sốt rét nặng nên phải đưa về gia đình, khi đó đã về ở Phú Nhuận, để điều trị. Trong thời gian điều trị, ông bắt đầu luyện tập chơi cờ trở lại và chẳng mấy chốc đã trở thành cao thủ nhất vùng. Nhiều kỳ thủ trẻ nghe danh đến khiêu chiến và hầu hết đều bại trận dưới sức cờ của ông. Do đặc điểm khuôn mặt khắc khổ và nước da tai tái bởi hậu chứng của bệnh sốt rét, nên mọi người thường gọi ông là Minh "rét".

Năm 1980, tại giải cờ mừng Xuân do Phòng Thể dục Thể thao Phú Nhuận tổ chức, Mai Thanh Minh, Nguyễn Văn Dũng và Lê Văn Kiết chia nhau những thứ hạng đầu. Tại buổi trao giải, một khách mời đã bất ngờ thách đấu với 3 người bằng cách đánh đồng loạt. Trận đấu đã thu hút nhiều người mê cờ kéo đến xem. Kết quả cuộc đấu biểu diễn hai bên hòa nhau, trong đó Mai Thanh Minh phải thủ hòa với vị khách.

Sau trận đấu biểu diễn này, ông nhận ra sức cờ của mình còn non kém. Ông tiếp tục tập luyện và thu thập nhiều nước cờ khác nhau để tăng sức cờ. Thời gian này, ông đã đến thụ giáo với danh thủ Phạm Thanh Mai. Trong suốt 5 năm, ông tham gia nhiều ván cờ không chính thức và đã đánh bại nhiều cao thủ làng cờ danh tiếng và được bạn cờ Sài Gòn đặt cho biệt danh "Độc cô cửu kiếm" do lối đánh đa dạng và biến hóa của mình.

Năm 1985, ông tham gia giải Vô địch cờ tướng Thành phố Hồ Chí Minh. Tại giải này, kỳ thủ được nhiều người tin tưởng sẽ giành chức vô địch là Trần Quới, nhưng bất ngờ, Trần Quới bị Nguyễn Văn Xuân đánh bại, rồi sau đó lại bị Lê Văn Bình cầm hòa. Nhờ thế, ông tận dụng ngay cơ hội, vượt lên đoạt chức vô địch. Từ đó kéo dài chuỗi huyền thoại của ông trong giới kỳ thủ cờ tướng Thành phố Hồ Chí Minh trong suốt 25 năm sau đó.